package com.xcc.dataStructures.demo11_binarysorttree;

/**
 * 排序二叉树
 */
public class BinarySortTreeDemo {

    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 8};

        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }

        System.out.println("中序遍历");
        binarySortTree.midOrder();

        binarySortTree.del(1);
        binarySortTree.del(3);
        binarySortTree.del(5);
        binarySortTree.del(7);
        binarySortTree.del(8);
        binarySortTree.del(9);
        binarySortTree.del(12);
        binarySortTree.del(10);
//        binarySortTree.del(9);
        System.out.println("刪除后为:");
        binarySortTree.midOrder();
    }

}

class BinarySortTree {
    private Node root;

    /**
     * 删除结点
     * 1)叶子结点直接删除
     * 2)有且仅有一个子节点(左或右)
     * 当前结点有左子树,当前节点是父节点的左节点  parent.left = target.left
     * 当前结点有左子树,当前节点是父节点的右节点  parent.right = target.left
     * 当前结点有右子树,当前节点是父节点的左节点  parent.left = target.right
     * 当前结点有右子树,当前节点是父节点的右节点  parent.right = target.right
     * 3)有两个子节点
     * 查找当前右子树的最左边结点使用临时变量temp，赋值target.value = temp.value
     * 删除temp
     */
    public void del(int value) {
        Node target = root.search(value);
        if (target == null) {
            return;
        }

        Node parent = root.searchParent(value);
        //1)叶子结点
        if (target.left == null && target.right == null) {
            //当前父节点为空，目标结点是叶子结点(目标结点是根节点)
            if (parent == null) {
                root = null;
                return;
            }
            if (parent.left == target) {
                parent.left = null;
            }
            if (parent.right == target) {
                parent.right = null;
            }

        }
        //2)存在两个叶子结点
        else if (target.left != null && target.right != null) {
            //找到右子树的最左结点，并删除它
            Node endNode = findLeft(target.right);
            del(endNode.value);
            //如果parent为null 则删除结点为根节点
            if (parent == null) {
                root = endNode;
            } else {
                if (parent.left == target) {
                    parent.left = endNode;
                }
                if (parent.right == target) {
                    parent.right = endNode;
                }
            }
            endNode.left = target.left;
            endNode.right = target.right;
        }
        //3)存在一个叶子结点
        else {
            if (target.left != null) {
                //当前删除为根节点,设置目标结点的左节点为根节点
                if (parent == null) {
                    root = target.left;
                    return;
                }
                if (parent.left == target) {
                    parent.left = target.left;
                } else {
                    parent.right = target.left;
                }
            }
            if (target.right != null) {
                if (parent == null) {
                    root = target.right;
                    return;
                }
                if (parent.left == target) {
                    parent.left = target.right;
                } else {
                    parent.right = target.right;
                }
            }
        }
    }

    /**
     * 查找最左结点
     */
    public Node findLeft(Node node) {
        if (node == null) {
            return null;
        }
        Node tmp = node;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        return tmp;
    }

    /**
     * 寻找当前值对应的结点
     */
    public Node search(int value) {
        return root.search(value);
    }

    /**
     * 寻找当前值的父节点
     */
    public Node searchParent(int value) {
        return root.searchParent(value);
    }

    /**
     * 添加
     */
    public void add(Node node) {
        if (root == null) {
            root = node;
            return;
        }
        root.add(node);
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        if (root == null) {
            System.out.println("二叉树为空，不能遍历");
            return;
        }
        root.midOrder();
    }

}

class Node {
    int value;
    Node left;
    Node right;

    /**
     * 查询目标结点的父节点
     */
    public Node searchParent(int val) {
        if (this.value > val && this.left != null) {
            //左节点为需要寻找的结点
            if (this.left.value == val) {
                return this;
            }
            return this.left.searchParent(val);
        }
        if (this.value < val && this.right != null) {
            if (this.right.value == val) {
                return this;
            }
            return this.right.searchParent(val);
        }
        return null;
    }

    /**
     * 查找当前结点
     */
    public Node search(int val) {
        if (this.value == val) {
            return this;
        }
        //如果查找的值小于当前值 并且 左子节点不为空 递归查找
        if (this.value > val && this.left != null) {
            return this.left.search(val);
        }
        if (this.value < val && this.right != null) {
            return this.right.search(val);
        }
        return null;
    }

    /**
     * 添加结点
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //如果当前节点值大于添加的值
        if (this.value > node.value) {
            //如果左节点不为空就向左递，否则就赋值给左节点
            if (this.left != null) {
                this.left.add(node);
            } else {
                this.left = node;
            }
        } else {
            if (this.right != null) {
                this.right.add(node);
            } else {
                this.right = node;
            }
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node[" +
                "value=" + value +
                ']';
    }
}
